package 中等.动态规划.其他;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这
 * 些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/get-kth-magic-number-lcci
 */
public class 第k个数_1709 {

    public static void main(String[] args) {

        System.out.println(getKthMagicNumber1(251));

    }

    /**
     * 最小堆
     * 取堆顶最小元素，将 min * 3 , min * 5 , min *7 入堆
     * 注意去重
     *
     * @param k
     * @return
     */
    public static int getKthMagicNumber1(int k) {
        int[] factors = {3, 5, 7};
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        priorityQueue.add(1L);
        Set<Long> set = new HashSet<>();
        set.add(1L);
        while (k-- > 1) {
            long min = priorityQueue.poll();
            for (int factor : factors) {
                if (!set.contains(min * factor)) {
                    priorityQueue.add(min * factor);
                    set.add(min * factor);
                }
            }
        }
        return priorityQueue.peek().intValue();
    }

    /**
     * TODO 动态规划
     * dp[i] 代表 第 i 个数为第 i 个最小丑数 （把只包含质因子2，3和5的数称作丑数）
     *
     * @param k
     * @return
     */
    public static int getKthMagicNumber(int k) {
        int[] dp = new int[k + 1];
        dp[1] = 1;
        Set<Integer> set = new HashSet<>();
        set.add(1);

        return dp[k];
    }

}
